﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Drawing2D;

namespace MaDiTuan
{
    public partial class Main : Form
    {
        ArrayElement AE;

        System.Drawing.Image image =  MaDiTuan.Properties.Resources.horse200;

        bool stop;
        int count;
        int num_result;
        int speed = 10;

        private int mouseX, mouseY;
        private Bitmap drawing;
        private Graphics g;
        private Pen p;

        private int x_begin = 0, y_begin = 0;
        private int rows_num, columns_num;
        private int size_row, size_column;

        public Main()
        {
            InitializeComponent();

            rows_num = Convert.ToInt16(numericUpDown1.Value);
            columns_num = Convert.ToInt16(numericUpDown2.Value);
            size_row = (this.Size.Height - 50) / (rows_num + 1);
            size_column = (this.Size.Width - 50) / (columns_num + 1);

            Draw_Backgroud();
        }

        private void button1_Click(object sender, EventArgs e)
        {
           
                stop = false;

                num_result = 0;
                count = 1;
                AE = new ArrayElement(rows_num,columns_num, x_begin, y_begin);
                AE.board[AE.row, AE.col] = count;
                AE.result[0].X = x_begin ;
                AE.result[0].Y = y_begin ;
                Find_solution();
        }

        private void Find_solution()
        {
            if (stop)
                return;
            if (count == rows_num * columns_num)
            {
                num_result++;
                if (MessageBox.Show("Result "+num_result.ToString() + " ? Watch or Quit","Ask", MessageBoxButtons.YesNo) == DialogResult.Yes)
                {
                    Draw_Solution();
                }
                else
                {
                    stop = true;
                }
                return;
            }
            AE.Possible();
            AE.Heuristic();
            int z = AE.accessible[AE.row, AE.col];
            for (int i = 0; i < z; i++)
            {

                int r = AE.row + AE.ver[AE.choice[AE.row, AE.col, 0]];
                int c = AE.col + AE.hor[AE.choice[AE.row, AE.col, 0]];
                int r_old = AE.row;
                int c_old = AE.col;
                AE.board[r, c] = count;
                AE.result[count].X = c;
                AE.result[count].Y = r;
                AE.row = r;
                AE.col = c;
                count++;

                Find_solution();

                count--;
                AE.board[r, c] = 0;
                AE.result[count].X = 0;
                AE.result[count].Y = 0;
                AE.row = r_old;
                AE.col = c_old;
            }
        }

        private void Draw_Backgroud()
        {
            if (drawing != null)
                drawing.Dispose();
            drawing = new Bitmap(this.Size.Width, this.Size.Height);
            g = Graphics.FromImage(drawing);
            Color c = Color.LightSeaGreen;
            p = new Pen(c, 2);
            g.Clear(Color.White);

            for (int i = 0; i < rows_num + 1; i++)
            {
                g.DrawLine(p, 50, 50 + i * size_row, 50 + size_column * columns_num, 50 + i * size_row);
            }
            for (int j = 0; j < columns_num + 1; j++)
            {
                g.DrawLine(p, 50 + j * size_column, 50, 50 + j * size_column, 50 + size_row * rows_num);
            }
            g.FillRectangle(Brushes.Red, 50 + x_begin * size_column + 3, 50 + y_begin * size_row + 3, size_column - 6, size_row - 6);
        }

        private void Draw_Solution()
        {
            for (int i = 0; i < count - 1 ; i++ )
            {
                Draw_Backgroud();
                for (int j = 1; j <= i; j++)
                {
                    g.FillRectangle(Brushes.Gray, 50 + AE.result[j].X * size_column + 3, 50 + AE.result[j].Y * size_row + 3, size_column - 6, size_row - 6);
                }
                g.FillRectangle(Brushes.Yellow, 50 + AE.result[i + 1].X * size_column + 3, 50 + AE.result[i + 1].Y * size_row + 3, size_column - 6, size_row - 6);
                g.SmoothingMode = SmoothingMode.None;
                g.DrawImage(image, 50 + AE.result[i].X * size_column + 3, 50 + AE.result[i].Y * size_row + 3, size_column - 6, size_row - 6);
                this.Refresh();

                System.Threading.Thread.Sleep(speed);
            }
        }

        protected override void OnPaint(PaintEventArgs e)
        {
            e.Graphics.SmoothingMode = SmoothingMode.None;
            e.Graphics.DrawImageUnscaled(drawing, 0, 0);
        }
        protected override void OnPaintBackground(PaintEventArgs e)
        {

        }
        private void Main_Resize(object sender, EventArgs e)
        {
            size_row = (this.Size.Height - 50) / (rows_num + 1);
            size_column = (this.Size.Width - 50) / (columns_num + 1);
            Draw_Backgroud();
            this.Refresh();
        }
        private void numericUpDown1_ValueChanged(object sender, EventArgs e)
        {
            rows_num = Convert.ToInt16(numericUpDown1.Value);
            size_row = (this.Size.Height - 50) / (rows_num + 1);
            Draw_Backgroud();
            this.Refresh();
        }
        private void numericUpDown2_ValueChanged(object sender, EventArgs e)
        {
            columns_num = Convert.ToInt16(numericUpDown2.Value);
            size_column = (this.Size.Width - 50) / (columns_num + 1);
            Draw_Backgroud();
            this.Refresh();
        }
        private void Main_MouseDown(object sender, MouseEventArgs e)
        {
            mouseX = e.X;
            mouseY = e.Y;
        }
        private void Main_MouseClick(object sender, MouseEventArgs e)
        {
                if (mouseX >= 50 && mouseX <= 50 + columns_num * size_column && mouseY >= 50 && mouseY <= 50 + rows_num * size_row)
                {
                    x_begin = (mouseX - 50) / size_column;
                    y_begin = (mouseY - 50) / size_row;
                    Draw_Backgroud();
                    this.Refresh();
                }
        }

        private void hScrollBar1_ValueChanged(object sender, EventArgs e)
        {
            speed = Convert.ToInt16( hScrollBar1.Value);
        }

    }
    public class ArrayElement
    {
        private int sizeX,sizeY;

        public int[] ver = { -1, -2, -2, -1, 1, 2, 2, 1 };
        public int[] hor = { 2, 1, -1, -2, -2, -1, 1, 2 };

        public int row, col; 
        public int[,] board; 
        public int[,,] choice; 
        public int[,] accessible;
        public Point[] result;

        public ArrayElement() { }
        public ArrayElement(int r_num,int c_num, int x_begin,int y_begin)
        {
            sizeY = r_num;
            sizeX = c_num;

            row = y_begin;
            col = x_begin;

            result = new Point[sizeX * sizeY];
            board = new int[sizeY, sizeX];
            choice = new int[sizeY, sizeX, 8];
            accessible = new int[sizeY, sizeX];
        }
        public void Possible()
        {
            int next_pos;
            for (int r = 0; r <= sizeY - 1; r++)
            {

                for (int c = 0; c <= sizeX - 1; c++)
                {
                    next_pos = 0;

                    for (int i = 0; i <= 7; i++)
                    {
                        if (((r + ver[i] >= 0) && (r + ver[i] <= sizeY - 1)) && ((c + hor[i] >= 0) && (c + hor[i] <= sizeX - 1)) && (board[r + ver[i],c + hor[i]] == 0))
                        {

                            choice[r,c,next_pos] = i;
                            next_pos++;
                        }
                    }
                    accessible[r,c] = next_pos;
                }
            }
        }
        public void Heuristic()
        {
            int min;
            int tmp;
            for (int i = 0; i < accessible[row, col]; i++)
            {
                tmp = i;
                min = accessible[row + ver[choice[row, col, i]], col + hor[choice[row, col, i]]];
                for (int j = i + 1; j < accessible[row, col]; j++)
                    if (accessible[row + ver[choice[row, col, j]], col + hor[choice[row, col, j]]] > 0 && 
                        min >= accessible[row + ver[choice[row, col, j]], col + hor[choice[row, col, j]]])
                    {
                        min = accessible[row + ver[choice[row, col, j]], col + hor[choice[row, col, j]]];
                        tmp = j;
                    }
                if (tmp != i)
                {
                    int k;
                    k = choice[row, col, tmp];
                    choice[row, col, tmp] = choice[row, col, i];
                    choice[row, col, i] = k;
                }     
            }
        }  
    }
}
